package Sort;

import com.google.common.collect.Lists;
import org.junit.Before;
import org.junit.Test;

import java.util.*;

/**
 * @Author: zhiping
 * @ClassName Bfs
 * @Date:2018/9/11 18:16
 * @Description: Breadth  First Search
 *  * 二叉树
 *  * 本例通过队列和遍历两种方式实现
 */
public class Bfs {
    private BinaryTreeNode headNode;

    /**
     * @MethodName initBinTree
     * @Date:2018/9/11 17:32
     * @Parm:[]
     * @Return:void
     * @Description: 构建一个二叉树
     */
    @Before
    public void initBinTree(){

        headNode = new BinaryTreeNode("A");
        BinaryTreeNode nodeB = new BinaryTreeNode("B");
        headNode.setLeft(nodeB);
        BinaryTreeNode nodeC = new BinaryTreeNode("C");
        headNode.setRight(nodeC);
        BinaryTreeNode nodeD = new BinaryTreeNode("D");
        BinaryTreeNode nodeE = new BinaryTreeNode("E");
        nodeB.setLeft(nodeD);
        nodeB.setRight(nodeE);
        BinaryTreeNode nodeI = new BinaryTreeNode("I");
        nodeE.setRight(nodeI);


        BinaryTreeNode nodeF = new BinaryTreeNode("F");
        BinaryTreeNode nodeG = new BinaryTreeNode("G");

        nodeC.setLeft(nodeF);
        nodeC.setRight(nodeG);
    }

    /**
     * @MethodName queueSearch
     * @Date:2018/9/11 18:17
     * @Parm:[]
     * @Return:void
     * @Description: 队列 先进先出遍历
     */
    @Test
    public void queueSearch(){

        LinkedList<BinaryTreeNode> nodeQueue = new LinkedList<BinaryTreeNode>() ;

        nodeQueue.push(headNode);

        while (!nodeQueue.isEmpty()){
            BinaryTreeNode tmpNode = nodeQueue.pop();
            System.out.println(tmpNode.getId());
            if(tmpNode.getLeft()!=null){
                nodeQueue.add(tmpNode.getLeft());
            }
            if(tmpNode.getRight()!=null){
                nodeQueue.add(tmpNode.getRight());
            }
        }
    }


    /**
     * @MethodName RecursiveSearch
     * @Date:2018/9/11 18:02
     * @Parm:[]
     * @Return:void
     * @Description: 递归实现
     * A
     * B
     * C
     * D
     * E
     * F
     * G
     * I
     */
    @Test
    public void recursiveSearch(){
        recursiveSearchInner(Arrays.asList(headNode));
    }

    private void recursiveSearchInner(List<BinaryTreeNode> tmpNodes){
        List<BinaryTreeNode> treeNodes = Lists.newArrayList();
        if(tmpNodes != null && tmpNodes.size()>0){
            for(BinaryTreeNode tmpNode : tmpNodes){
                System.out.println(tmpNode.getId());
                if(tmpNode.getLeft()!=null){
                    treeNodes.add(tmpNode.getLeft());
                }
                if(tmpNode.getRight()!=null){
                    treeNodes.add(tmpNode.getRight());
                }
            }
        }
        if(treeNodes.size()>0){
            recursiveSearchInner(treeNodes);
        }

    }

}
